# 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
#
# 有效字符串需满足：
#   1. 左括号必须用相同类型的右括号闭合。
#   2. 左括号必须以正确的顺序闭合。
#   3. 每个右括号都有一个对应的相同类型的左括号。
#
# 示例 1：
#
# 输入：s = "()"
# 输出：true
# 示例 2：
#
# 输入：s = "()[]{}"
# 输出：true
# 示例 3：
#
# 输入：s = "(]"
# 输出：false
from typing import List


class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for ch in s:
            if ch == '(' or ch == '[' or ch == '{':
                stack.append(ch)
            elif ch == ')':
                if len(stack) > 0:
                    if stack[-1] != '(':
                        return False
                    else:
                        stack.pop()
                else:
                    return False
            elif ch == ']':
                if len(stack) > 0:
                    if stack[-1] != '[':
                        return False
                    else:
                        stack.pop()
                else:
                    return False
            else:
                if len(stack) > 0:
                    if stack[-1] != '{':
                        return False
                    else:
                        stack.pop()
                else:
                    return False
        return len(stack) == 0


if __name__ == '__main__':
    s = '()[]{}'
    # s = "()"
    # s = "(]"
    # s = "]"
    print(Solution().isValid(s))
